package com.lw.leetcode.dp.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * <p>
 * dp
 * 983. 最低票价
 *
 * @author liw
 * @version 1.0
 * @date 2021/7/30 14:11
 */
public class MincostTickets {

    public static void main(String[] args) {
        MincostTickets test = new MincostTickets();

//        String str = "aabbabc";
//        int k = 3;

        // 输入：days = [1,4,6,7,8,20], costs = [2,7,15]    11

//        int[] days = {1,4,6,7,8,20};
//        int[] costs = {2,7,15};
        //
        //输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]     17

        int[] days = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31};
        int[] costs = {2, 7, 15};

        int i = test.mincostTickets(days, costs);
        System.out.println(i);
    }

    public int mincostTickets(int[] days, int[] costs) {
        int a = costs[0];
        int b = costs[1];
        int c = costs[2];

        int length = days.length;
        int[] arr = new int[length + 1];
        Arrays.fill(arr, Integer.MAX_VALUE);
        arr[0] = 0;
        for (int i = 0; i < length; i++) {
            int day = days[i];
            arr[i + 1] = Math.min(arr[i] + a, arr[i + 1]);
            int j = i + 1;
            while (j <= length && days[j - 1] <= day + 6) {
                arr[j] = Math.min(arr[i] + b, arr[j]);
                j++;
            }
            j = i + 1;
            while (j <= length && days[j - 1] <= day + 29) {
                arr[j] = Math.min(arr[i] + c, arr[j]);
                j++;
            }
        }
        return arr[length];
    }

}
